{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Smallest Letter Greater Than Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nextGreatestLetter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找比目标字母大的最小字母"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符数组 <code>letters</code>，该数组按<strong>非递减顺序</strong>排序，以及一个字符 <code>target</code>。<code>letters</code>&nbsp;里<strong>至少有两个不同</strong>的字符。</p>\n",
    "\n",
    "<p>返回&nbsp;<code>letters</code>&nbsp;中大于 <code>target</code> 的最小的字符。如果不存在这样的字符，则返回&nbsp;<code>letters</code> 的第一个字符。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>letters = [\"c\", \"f\", \"j\"]，target = \"a\"\n",
    "<strong>输出:</strong> \"c\"\n",
    "<strong>解释：</strong>letters 中字典上比 'a' 大的最小字符是 'c'。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> letters = [\"c\",\"f\",\"j\"], target = \"c\"\n",
    "<strong>输出:</strong> \"f\"\n",
    "<strong>解释：</strong>letters 中字典顺序上大于 'c' 的最小字符是 'f'。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> letters = [\"x\",\"x\",\"y\",\"y\"], target = \"z\"\n",
    "<strong>输出:</strong> \"x\"\n",
    "<strong>解释：</strong>letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= letters.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>letters[i]</code>&nbsp;是一个小写字母</li>\n",
    "\t<li><code>letters</code> 按<strong>非递减顺序</strong>排序</li>\n",
    "\t<li><code>letters</code> 最少包含两个不同的字母</li>\n",
    "\t<li><code>target</code> 是一个小写字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-smallest-letter-greater-than-target](https://leetcode.cn/problems/find-smallest-letter-greater-than-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-smallest-letter-greater-than-target](https://leetcode.cn/problems/find-smallest-letter-greater-than-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"c\",\"f\",\"j\"]\\n\"a\"', '[\"c\",\"f\",\"j\"]\\n\"c\"', '[\"x\",\"x\",\"y\",\"y\"]\\n\"z\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters, target):\n",
    "        left = 0\n",
    "        right = len(letters) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if letters[mid] <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return letters[left] if left < len(letters) else letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters, target):\n",
    "        \"\"\"\n",
    "        :type letters: List[str]\n",
    "        :type target: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        left, right = 0, len(letters) - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if letters[mid] <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                if mid < 1 or (mid >= 1 and letters[mid-1] <= target):\n",
    "                    return letters[mid]\n",
    "                right = mid - 1\n",
    "        return letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters, target):\n",
    "        \"\"\"\n",
    "        :type letters: List[str]\n",
    "        :type target: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        for c in letters:\n",
    "            if c > target:\n",
    "                return c\n",
    "        return letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters, target):\n",
    "        \"\"\"\n",
    "        :type letters: List[str]\n",
    "        :type target: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        letters=sorted(list(set(letters)))\n",
    "        for i in letters:\n",
    "            if i >target:\n",
    "                return i\n",
    "        return letters[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        index = bisect.bisect(letters, target)\n",
    "        return letters[index % len(letters)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "                \n",
    "        assert len(letters)>=2\n",
    "        assert len(letters)<=10000\n",
    "\n",
    "        left, right = 0, len(letters)-1\n",
    "        while left<right:\n",
    "            mid = (left+right)//2 # left mid index\n",
    "            if target == letters[mid]:\n",
    "                left = mid+1\n",
    "            elif target < letters[mid]:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "\n",
    "        if letters[right] <= target:\n",
    "            right +=1\n",
    "        return letters[(right)%len(letters)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        # for ch in letters:\n",
    "        #     if ch > target:\n",
    "        #         return ch\n",
    "        # return letters[0]\n",
    "\n",
    "        # index = bisect.bisect(letters, target)\n",
    "        # return letters[index % len(letters)]\n",
    "\n",
    "        seen = set(letters)\n",
    "        for i in range(1, 26):\n",
    "            cand = chr((ord(target) - ord('a') + i) % 26 + ord('a'))\n",
    "            if cand in seen:\n",
    "                return cand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        from string import ascii_lowercase\n",
    "        temp = ascii_lowercase * 2\n",
    "        ind = temp.index(target)\n",
    "        for ch in temp[ind+1:]:\n",
    "            if ch in letters:\n",
    "                return ch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        length=len(letters)\n",
    "        l,r=0,length-1\n",
    "        if target<letters[l]:\n",
    "            return letters[l]\n",
    "        if target>=letters[r]:\n",
    "            return letters[l]\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if letters[mid]<=target:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return letters[l]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        n = len(letters)\n",
    "        l, h = 0, n - 1\n",
    "        while l <= h:\n",
    "            m = l + (h - l)//2\n",
    "            if letters[m] <= target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                h = m - 1\n",
    "        return letters[l] if l < n else letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        return letters[bisect.bisect(letters,target)%len(letters)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        '''\n",
    "        length = len(letters)\n",
    "        left = 0\n",
    "        right = length-1\n",
    "        while(left<=right):\n",
    "            mid = (left+right)//2\n",
    "            if letters[mid]>target:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        if left == length:\n",
    "            return letters[0]\n",
    "        else:\n",
    "            return letters[left]\n",
    "        '''\n",
    "\n",
    "        length = len(letters)\n",
    "        left = 0\n",
    "        right = length-1\n",
    "        while(left<=right):\n",
    "            mid = (left+right)//2\n",
    "            if letters[mid]>target:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        if left == length:\n",
    "            return letters[0]\n",
    "        else:\n",
    "            return letters[left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        for c in letters:\n",
    "            if c>target:\n",
    "                return c\n",
    "        return letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        l = [x > target for x in letters]\n",
    "        return letters[l.index(max(l))]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        return min(letters, key = lambda x:  t+ 26 if (t:=ord(x) - ord(target)) <= 0 else t )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters, target: str) -> str:\n",
    "        n = len(letters)\n",
    "        h = n-1\n",
    "        l = 0\n",
    "        while l <= h:\n",
    "            m = int(l + (h-l)/2)\n",
    "            if letters[m] <= target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                h = m - 1\n",
    "        return letters[l] if l<n else letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters, target: str) -> str:\n",
    "        n = len(letters)\n",
    "        h = n-1\n",
    "        l = 0\n",
    "        while l <= h:\n",
    "            m = int(l + (h-l)/2)\n",
    "            if letters[m] <= target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                h = m - 1\n",
    "        return letters[l] if l<n else letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters, target: str) -> str:\n",
    "        for items in letters:\n",
    "            if target < items:\n",
    "                return items\n",
    "        return letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        letters.append(target)\n",
    "        for i in range(len(letters)):\n",
    "            letters[i] = ord(letters[i])\n",
    "        tar = ord(target)\n",
    "        letters.sort()\n",
    "        for num in letters:\n",
    "            if num > tar:\n",
    "                return chr(num)\n",
    "        return chr(letters[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        for i in range(len(letters)):\n",
    "            letters[i] = ord(letters[i])\n",
    "        target = ord(target)\n",
    "        pos = bisect.bisect_right(letters, target)\n",
    "        \n",
    "        if pos == len(letters):\n",
    "            return chr(letters[0])\n",
    "        return chr(letters[pos])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters, target: str) -> str:\n",
    "        num = 0\n",
    "        for item in letters:\n",
    "            letters[num] = ord(item)\n",
    "            num += 1\n",
    "        target = ord(target)\n",
    "        num -= 1\n",
    "        \n",
    "        if target >= letters[num]:\n",
    "            return chr(letters[0])\n",
    "\n",
    "        left = 0\n",
    "        right = num\n",
    "        while right-left > 1:\n",
    "            mid = (left+right)//2\n",
    "            \n",
    "            if target < letters[mid]:\n",
    "                right = mid \n",
    "            elif target > letters[mid]:\n",
    "                left = mid\n",
    "            else:\n",
    "                while target >= letters[mid]:\n",
    "                    mid += 1\n",
    "                return chr(letters[mid])\n",
    "        mid = left\n",
    "        while target >= letters[mid]:\n",
    "            mid += 1\n",
    "        return chr(letters[mid])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        head = letters[0]\n",
    "        while len(letters) > 0:\n",
    "            if letters[0] <= target:\n",
    "                letters.pop(0)\n",
    "            else:\n",
    "                return letters[0]\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        return letters[bisect_right(letters,target) if target<letters[-1] else 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "                for letter in letters:\n",
    "                    if letter > target:\n",
    "                        return letter\n",
    "                    # else:\n",
    "                    #     return letters[0]\n",
    "                return letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        for letter in letters:\n",
    "            if (target<letter) :return letter\n",
    "        return letters[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        left = 0\n",
    "        right = len(letters) - 1\n",
    "        if target >= letters[right]:\n",
    "            return letters[0]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if letters[mid] > target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return letters[left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        return letters[r] if (r := bisect_right(letters, target)) < len(letters) else letters[0]\n",
    "        # bisect_right返回大于x的第一个下标，bisect_left返回大于等于x的第一个下标，但使用前提是列表有序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreatestLetter(self, letters: List[str], target: str) -> str:\n",
    "        left=0\n",
    "        right=len(letters)-1\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if letters[mid]==target:\n",
    "                left=mid\n",
    "                break \n",
    "            if target>letters[mid]:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        while left<len(letters) and letters[left]==target:\n",
    "            left+=1\n",
    "        if left==len(letters):\n",
    "            return letters[0]\n",
    "        return letters[left]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
